#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/3 10:07
# @USER    : Shengji He
# @File    : 3Sum.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        """
        Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0?
        Find all unique triplets in the array which gives the sum of zero.

        Note:
        The solution set must not contain duplicate triplets.

        :param nums: List[int]
        :return: List[List[int]]

        Example:
            Given array nums = [-1, 0, 1, 2, -1, -4],

            A solution set is: [[-1, 0, 1], [-1, -1, 2]]
        """
        # ans = []
        # targets = []
        # for j in range(len(nums)):
        #     target = nums.pop(0)
        #     if target in targets:
        #         continue
        #     targets.append(target)
        #     cmp = nums.copy()
        #     for i in range(len(cmp)):
        #         b = cmp.pop(0)
        #         c = -target - b
        #         if c in cmp:
        #             temp = [target, b, c]
        #             temp.sort()
        #             if temp in ans:
        #                 continue
        #             ans.append(temp)
        # return ans
        ans = []
        nums.sort()
        for i in range(len(nums) - 2):
            if nums[i] > 0:
                return ans
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            s, e = i + 1, len(nums) - 1
            while s < e:
                if nums[s] + nums[e] + nums[i] == 0:
                    ans.append([nums[i], nums[s], nums[e]])
                    while s < e and nums[s] == nums[s + 1]:
                        s += 1
                    while s < e and nums[e] == nums[e - 1]:
                        e -= 1
                    s += 1
                    e -= 1
                elif nums[s] + nums[e] + nums[i] > 0:
                    while s < e and nums[e] == nums[e - 1]:
                        e -= 1
                    e -= 1
                else:
                    while s < e and nums[s] == nums[s + 1]:
                        s += 1
                    s += 1
        return ans


if __name__ == '__main__':
    S = Solution()
    nums = [-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0]
    # nums = [-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6]
    # nums = [3, 0, -2, -1, 1, 2]
    # nums = [-2, 0, 1, 1, 2]
    # nums = [-1, 0, 1, 2, -1, -4]
    print(S.threeSum(nums))
    print('done')
